1. Field
Example embodiments relate to a path planning apparatus planning an optimal path while satisfying a dynamic constraint, and a method and computer-readable medium thereof.
2. Description of the Related Art
In general, a mechanical device which performs motion similar to human motion using an electrical or magnetic mechanism is called a robot. Early robots included manipulators used for automated or unmanned tasks in manufacturing plants or industrial robots such as transportation robots. Robots also performed dangerous tasks, repetitive tasks or performed tasks requiring a large amount of force. Recently, research into a humanoid robot, which has joints similar to those of a human, and coexists with a human in a working and living space of the human to provide various services, has been actively conducted.
Such a humanoid robot performs tasks using a manipulator which may move similar to the arm or hand motion of a human by an electrical or mechanical mechanism. In most manipulators which are currently in use, several links are connected to each other. A connection portion between the links is called a joint. The motion characteristics of the manipulator are determined according to a geometrical relationship. Mathematical representation of such a geometrical relationship is called kinematics. In general, the manipulator moves an end effector of a robot with such kinematic characteristics in a direction (goal point) to perform a task.
In order to allow the manipulator to perform a given task (e.g., grasp an object), it is important to generate a motion path of the manipulator from an initial position (start point) before the manipulator performs a task to a final position (goal point) where the task may be performed, for example, where an object may be grasped. An example of a sampling based path planning method of planning a path to connect a start point and a goal point while satisfying a constraint such as collision avoidance where a manipulator does not collide with an obstacle within a working area includes a Rapidly-exploring Random Tree (RRT) algorithm.
The RRT algorithm uses a randomly sampled configuration in a Configuration Space (C-Space), where a manipulator or a humanoid robot performs a task. An example of the RRT algorithm includes a method of repeating a process of selecting a closest node from an initial start point to extend a tree and searching for a motion path to find a goal point. A node having a smallest goal score is selected from the tree using a goal function including a function of a distance from the goal point to an end-effector and a directional vector to extend the tree.
However, in the RRT algorithm of the related art, a closest node is selected without considering a dynamic constraint with time, i.e., a speed or balance, to extend a tree and generate a path. Speed and balance are then adjusted using an auto balancer. As a result, since the balance is not considered while the path is being generated, a path needs to be regenerated if the speed and balance are not adjusted using the auto balancer. Therefore, a speed to find a path is decreased and a time to plan a final path is increased.
Accordingly, as a method of considering a dynamic state when a path is generated, a method of calculating torque of a selected node and discarding the selected node if a predetermined torque constraint is not satisfied has been suggested. However, since this method does not consider time, a convergence speed is decreased if a dimension is increased. In addition, in a dynamic state where speed or balance is important, a constraint is not satisfied.